0606. 根据二叉树创建字符串【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 前序遍历

1. 📝 题目描述

• leetcode

给你二叉树的根节点 root，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

---

示例 1：

输入：root = [1,2,3,4]
输出："1(2(4))(3)"
解释：初步转化后得到 "1(2(4)())(3()())"，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)"。

示例 2：

输入：root = [1,2,3,null,4]
输出："1(2()(4))(3)"
解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。

---

提示：

• 树中节点的数目范围是 [1, 10^4]
• -1000 <= Node.val <= 1000

2. 🎯 s.1 - 前序遍历

c

char* tree2str(struct TreeNode* root) {
    if (!root) { char* s = (char*)malloc(1); s[0] = '\0'; return s; }
    char* left = tree2str(root->left);
    char* right = tree2str(root->right);
    char* res = (char*)malloc(100000);
    if (!root->left && !root->right) {
        sprintf(res, "%d", root->val);
    } else if (!root->right) {
        sprintf(res, "%d(%s)", root->val, left);
    } else {
        sprintf(res, "%d(%s)(%s)", root->val, left, right);
    }
    free(left); free(right);
    return res;
}

js

/**
 * @param {TreeNode} root
 * @return {string}
 */
var tree2str = function (root) {
  if (!root) return ''
  const left = tree2str(root.left)
  const right = tree2str(root.right)
  if (!left && !right) return '' + root.val
  if (!right) return `${root.val}(${left})`
  return `${root.val}(${left})(${right})`
}

py

class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:
        if not root:
            return ''
        left = self.tree2str(root.left)
        right = self.tree2str(root.right)
        if not left and not right:
            return str(root.val)
        if not right:
            return f'{root.val}({left})'
        return f'{root.val}({left})({right})'

• 时间复杂度：$O(n)$，其中 n 是二叉树的节点数
• 空间复杂度：$O(n)$，递归栈深度

算法思路：

• 前序遍历二叉树，递归构建字符串
• 若左右子树都为空，只输出值；若右子树为空，只需左括号；否则左右括号都需要